home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / cgazv5n4.arc / HZIP.C < prev    next >
C/C++ Source or Header  |  1991-09-23  |  11KB  |  395 lines
  1. /*--- Listing 2 -------------------------- HZIP.C --------------
  2.  * Author:     Anton Kruger,   5 October, 1990
  3.  *
  4.  * Copyright (c) Truda Software
  5.  *
  6.  * Source code may be freely used if authorship is acknowledged.
  7.  * Object code form may be used freely.
  8.  *
  9.  * Description:   Routines that perform Huffman compression.
  10.  *
  11.  * Compilers:     Turbo C++ 1.0, MSC 6.0
  12.  *
  13.  * Memory models: Any.
  14.  *
  15.  * Compile time switches:
  16.  *         MAIN  - if defined, a driver is provided
  17.  *         DEBUG - if defined, the Huffman tree is displayed
  18.  *
  19.  * Compile notes: The encode() routine needs a little over 2K
  20.  *         of stack space for its local variables. Turbo C's
  21.  *         default stack size is adequate at 4K, but Microsoft
  22.  *         only allocates 2K. To compile with Microsoft, you
  23.  *         must increase the stack size with commands like:
  24.  *
  25.  *                    cl   /W3 /DMAIN hzip.c
  26.  *                    link /STACK:0x1000 hzip.obj,hzip.exe;
  27.  *------------------------------------------------------------*/
  28.  
  29. #include <stdio.h>
  30. #include "huff.h"
  31.  
  32. int   huff_zip(char *infile,char *outfile);
  33. void  build_table(FILE *fp1);
  34. void  build_tree(void);
  35. void  write_head(FILE *fp);
  36. void  encode(FILE *fp1,FILE *fp2);
  37. void  build_codes(int (*codes)[2]);
  38. void  pack(int ib,int bits,FILE *fp);
  39. void  error(char *s);
  40.  
  41. #if defined(DEBUG)
  42. void  dump_tree(void);
  43. #endif
  44.  
  45. #if defined(DEBUG) || defined(MAIN)
  46. #include <stdlib.h>
  47. #include <string.h>
  48. #endif
  49.  
  50. #if defined(MAIN)
  51. /* A small driver for the Huffman compression subroutine */
  52. void main(int argc, char* argv[])
  53. {
  54.     int i;
  55.  
  56.     if (argc < 3)
  57.         error("Usage: HZIP infile outfile");
  58.     else{
  59.         i = huff_zip(argv[1],argv[2]);
  60.         switch (i){
  61.             case -1:
  62.                 error("could not open input file...");
  63.                 break;
  64.             case -2:
  65.                 error("could not open output file...");
  66.                 break;
  67.             default:
  68.                 ;
  69.         }
  70.     }
  71.     exit(0);
  72. }
  73. #endif
  74.  
  75. int huff_zip(char *infile,char *outfile)
  76. {
  77.     /*
  78.      * This routine compresses "infile" with the Huffman
  79.      * algorithm. The output is written to the file "outfile".
  80.      *
  81.      * Return values:
  82.      *                  0:   normal return
  83.      *                 -1:   could not open "infile"
  84.      *                 -2:   could not open "outfile"
  85.      */
  86.  
  87.     FILE  * fp1,*fp2;
  88.  
  89.     /* Open I/O files with enlarged buffers for efficiency */
  90.  
  91.     if ((fp1 = fopen(infile,"r+b")) != NULL)
  92.         setvbuf(fp1,NULL,_IOFBF,BUFFER_SIZE);
  93.     else
  94.         return(-1);
  95.     if ((fp2 = fopen(outfile,"w+b")) != NULL)
  96.         setvbuf(fp2,NULL,_IOFBF,BUFFER_SIZE);
  97.     else{
  98.         fclose(fp1);
  99.         return(-2);
  100.     }
  101.  
  102.         /* Build symbol frequency table for "fname" */
  103.     build_table(fp1);
  104.         /* Build Huffman tree using frequency tables */
  105.     build_tree();
  106.     write_head(fp2);  /* Write file header to output file */
  107.     encode(fp1,fp2);  /* Encode using Huffman tree */
  108.     fclose(fp1);      /* Clean up, and return to caller */
  109.     fclose(fp2);
  110.     return(0);
  111. }
  112.  
  113. void build_table(FILE* fp1)
  114. {
  115.     /*
  116.      * This routine makes the symbol frequency tables needed
  117.      * to build the Huffman tree. It also determines number of
  118.      * characters in the input file, "nchars", as well as
  119.      * number of unique symbols, "nsymbols".
  120.      */
  121.  
  122.     int   i,j;
  123.     int   indx;
  124.  
  125.     for (i=0;i<=MAXSYM-1;i++) /* Clear the frequency table */
  126.         freq[i] = 0;
  127.  
  128.     /* Count # of times a character occur in the input file */
  129.  
  130.     indx = getc(fp1);
  131.     while (!feof(fp1)){
  132.         freq[indx]++;
  133.         indx = getc(fp1);
  134.     }
  135.     rewind(fp1);
  136.  
  137.     /* Determine # of chars in input file */
  138.     for (nchars=0,i=0;i<=MAXSYM-1;i++)
  139.         nchars = nchars + freq[i];
  140.  
  141.     /* Initialize the "symbol"s table */
  142.     for (i=0;i<=MAXSYM-1;i++)
  143.         symbol[i] = (unsigned char)i;
  144.  
  145.     /*
  146.      * Pack the tables so that they are contiguous in memory.
  147.      * That is, the tables occupy the first block of elements
  148.      * in their respective arrays.
  149.      */
  150.  
  151.     for(i=0,j=0;j<=MAXSYM-1;j++){
  152.         if (freq[j] != 0) { /* => symbol occurs in input file */
  153.             freq[i] = freq[j];
  154.             symbol[i] = symbol[j];
  155.             if (i!=j) freq[j] = 0;
  156.             i++;
  157.         }
  158.     }
  159.     nsymbols = i;
  160. }
  161.  
  162. void build_tree(void)
  163. {
  164.     /* This routine builds the Huffman tree */
  165.  
  166.     int            root; /* Location of the root of the tree */
  167.     int            j,m;
  168.     int            n1,n2;
  169.     unsigned long  small1,small2;
  170.  
  171.  
  172.     /* Initialize the Huffman tree */
  173.  
  174.     root = (2*nsymbols-1) - 1;
  175.     for (j=0;j<=root;j++)
  176.         father[j] = left_son[j] = right_son[j] = NONE;
  177.  
  178.     /* Build Huffman tree */
  179.  
  180.     for (m=nsymbols;m<=root;m++){
  181.  
  182.         small1 = small2 = ULONG_MAX;
  183.  
  184.         /* Search for smallest node with no father */
  185.  
  186.         for (j=0; j<=m-1; j++){
  187.             if (father[j] == NONE){
  188.                 if (freq[j] < small1 && freq[j] != 0){
  189.                     small1 = freq[j];
  190.                     n1 = j;
  191.                 }
  192.             }
  193.         }
  194.  
  195.         /* Search for the second most smallest node
  196.             with no father */
  197.  
  198.         for (j=0; j<=m-1; j++){
  199.             if (father[j] == NONE){
  200.                 if (freq[j] < small2 &&
  201.                     freq[j] >= small1 && j != n1){
  202.                     small2 = freq[j];
  203.                     n2 = j;
  204.                 }
  205.             }
  206.         }
  207.  
  208.         /* Build a new node */
  209.  
  210.         left_son[m]  = n1;  /* Found a (left) son at node n1  */
  211.         right_son[m] = n2;  /* Found a (right) son at node n2 */
  212.         father[n1]   = m;   /* node n1's father is node m     */
  213.         father[n2]   = m;   /* node n2's father is node m     */
  214.         freq[m] = freq[n1]+freq[n2]; /* father has combined
  215.                                         frequency  of sons    */
  216.     }
  217.  
  218.     #if defined(DEBUG)
  219.     dump_tree();
  220.     #endif
  221. }
  222.  
  223. void write_head (FILE * fp)
  224. {
  225.     /*
  226.      * This routine writes the file header to the output file.
  227.      * The header starts off with three identification bytes
  228.      * that the decompression routine must check before
  229.      * attempting decoding. Following this are the components
  230.      * of the Huffman tree that are needed for decoding.
  231.      */
  232.  
  233.     int root;
  234.  
  235.     /* Write the characters "CH1" */
  236.  
  237.     putc('C',fp); /* ID Byte */
  238.     putc('H',fp); /* => Huffman encoding */
  239.     putc('1',fp); /* Version 1  */
  240.  
  241.     root = (2*nsymbols-1) - 1;
  242.     fwrite(&nchars,sizeof(nchars),1,fp);
  243.     fwrite(&root,sizeof(root),1,fp);
  244.     fwrite(left_son,sizeof(left_son[1]),root+1,fp);
  245.     fwrite(right_son,sizeof(right_son[1]),root+1,fp);
  246.     fwrite(&nsymbols,sizeof(nsymbols),1,fp);
  247.     fwrite(symbol,sizeof(symbol[1]),nsymbols,fp);
  248. }
  249.  
  250. void encode(FILE *fp1, FILE *fp2)
  251. {
  252.     /*
  253.      * This routine encodes the input file. First, the routine
  254.      * "build_codes" is called to set up a table that holds the
  255.      * Huffman code for each symbol in the input file. For each
  256.      * character in the input file the corresponding code is
  257.      * looked up, and packed away in the output file.
  258.      */
  259.  
  260.     int      codes[MAXNOD][2];
  261.     int      i,ib,bits;
  262.     unsigned long k;
  263.  
  264.             /* Generate Huffman "code"s table for file   */
  265.     build_codes(codes);
  266.     for (k=1;k<=nchars;k++){
  267.             /* Get a character from the input file       */
  268.         i = (int)getc(fp1);
  269.             /* Look up character's Huffman code          */
  270.         bits = codes[i][0];
  271.             /* Look up the number of bits in code        */
  272.         ib   = codes[i][1];
  273.             /* Pack character's code away in output file */
  274.         pack(ib,bits,fp2);
  275.     }
  276.  
  277.     /*
  278.      * The stream of bits may not make up an integral number
  279.      * of bytes, so some bits may remain unwritten. Flush all
  280.      * bits by writing 16 zero bits; this will also make the
  281.      * last byte in the output file 0.
  282.      */
  283.  
  284.     bits = 0;
  285.     pack(15,bits,fp2);
  286. }
  287.  
  288. void build_codes(int codes[][2])
  289. {
  290.     /*
  291.      * This routine fills the table "codes" with the Huffman
  292.      * codes for the input file. It starts at a symbol's
  293.      * terminal node, and moves up the tree until the root is
  294.      * reached (i.e., father == NONE), collecting "1" bits if
  295.      * the current node is a left son, or "0" bits otherwise.
  296.      * This procedure is repeated for all symbols.
  297.      */
  298.  
  299.     int      ib,bits;
  300.     int      j,node;
  301.     unsigned char k;
  302.  
  303.     for (j=0;j<=nsymbols-1;j++){
  304.         bits = ib = 0;
  305.         node = j;
  306.         while (father[node] != NONE){
  307.             if (node==left_son[father[node]])
  308.                     /* set bit if node is a left son   */
  309.                 bits = (int)ibset(bits,ib);
  310.             else    /* leave bit cleared if right son  */
  311.                 ;
  312.             ib++;
  313.                     /* move up one node closer to root */
  314.             node = father[node];
  315.         }
  316.  
  317.         ib--;
  318.         k = symbol[j];
  319.         codes[k][0] = bits; /* Store code for symbol[j] */
  320.         codes[k][1] = ib;   /* Store # of bits in code
  321.                                           for symbol[j] */
  322.     }
  323. }
  324. void pack(int ib,int bits,FILE* fp)
  325. {
  326.     /*
  327.      * This routine starts at bit-position "ib" in "bits"
  328.      * and scans for set bits. For every set bit found,
  329.      * a corresponding bit is set in "byte".
  330.      * When "byte" is full, it is written to the output file.
  331.      */
  332.  
  333.     static   char ip = 7; /* Keeps track of next
  334.                              open bit in "byte" */
  335.     static   char byte = 0;
  336.  
  337.     while (ib >= 0){
  338.         byte = btest(bits,ib) ? (char)ibset(byte,ip) : byte;
  339.         if (--ip < 0){
  340.             putc(byte,fp);
  341.             byte = 0;
  342.             ip = 7;
  343.         }
  344.         ib--;
  345.     }
  346. }
  347. void error(char *s)
  348. {
  349.     fprintf(stderr,"Error: %s\n",s);
  350.     exit(-1);
  351. }
  352.  
  353. #ifdef DEBUG
  354. /* debugging routine - displays contents of tree */
  355. void dump_tree(void)
  356. {
  357.     int   root,i;
  358.     int   c;
  359.     char  str[10];
  360.  
  361.     root = (2*nsymbols-1) - 1;
  362.     printf("******************************"
  363.            "******************************\n");
  364.     printf("   i  symbol   freq(i)  father(i)"
  365.            "  left_son(i)  right_son(i)\n");
  366.     printf("******************************"
  367.            "******************************\n");
  368.     for (i=0; i<=root; i++){
  369.         if (i == nsymbols)
  370.             printf("----------------------------"
  371.                    "--------------------------------\n");
  372.         c = symbol[i];
  373.         str[0] = (char) c;
  374.         str[1] = '\0';
  375.         if ((int)c == 0)  strcpy(str,"NULL");
  376.         if ((int)c == 7)  strcpy(str,"BELL");
  377.         if ((int)c == 8)  strcpy(str,"BS");
  378.         if ((int)c == 9)  strcpy(str,"TAB");
  379.         if ((int)c == 10) strcpy(str,"LF");
  380.         if ((int)c == 11) strcpy(str,"VT");
  381.         if ((int)c == 12) strcpy(str,"FF");
  382.         if ((int)c == 13) strcpy(str,"CR");
  383.         if ((int)c == 26) strcpy(str,"EOF");
  384.         if ((int)c == 32) strcpy(str,"SPACE");
  385.         if (i >= nsymbols)
  386.             str[0] = '\0';
  387.         printf("%4d  %5s %7d %8d %11d %13d\n",i,
  388.             str,
  389.             (int)freq[i],
  390.             (int)father[i],
  391.             (int)left_son[i],
  392.             (int)right_son[i]);
  393.     }
  394. }
  395. #endif